COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	CS206 MIDTERM
C00010 ENDMK
C⊗;
CS206 MIDTERM

There are a total of  60 points, and you  should allot roughly one  minute
per point; this will  give you 15  extra minutes at the  end to look  over
your work.  Partial credit will be given, so try every problem!  There  is
an optional question  for an extra  3 points (#2c)  which you should  only
work on if you have spare time.


1. Consider a function RDAC[u] which returns the next-to-the-last element of a list
	u.  Thus RDAC[(A B C D E)] is D.
   (a) [5 pts] Write a recursive version of RDAC in internal notation.
   (b) [4 pts] Rewrite the same function in external notation.
   (b) [5 pts] What did you assume about the argument to RDAC? Add some line(s)
	of code to (either form of) the function so it can accept any argument, 
	and will print out helpful messages in case the argument is inappropriate.


2. Consider the following structure in memory:


















	
   (a) [4pts] Write the corresponding S-expression in dot notation.
   (b) [6pts] How could such a "shared structure" have been created?
	Answer this by writing an S-expression (or a sequence of them) which,
	when evaluated, would return the above structure as the value.
   (c) OPTIONAL: There are two distinct ways (at least) to set up the structure.
	One of them involves doing a SETQ and some other even nastier things,
	and one of them is pure LISP involving nothing more unclean than a LAMBDA.
	Try to find the second way (i.e., the way other than the one you found 
	for part (b)).  This is worth an extra 3 points if you do it.


3. [15pts] In many applications, it's important for a program to treat novices dif-
	ferently from experienced users.  Often, the only change will be that the
	expert sees merely some subset of each prompt that the novice sees.  E.g.,
	the novice might at some point get the following message: "Please type
	in to me a function name I can use; make it less than 12 characters : ",
	while an expert in the same situation would have received the much more
	curt message  "function name : ".  One way to denote this might be to
	call upon a special conditional-printing function, with the novice's
	extraneous text set off in parentheses.  Thus we could have called
	(CPRINT '(Please type in to me a) function name (I can use; make it
	less than 12 characters) :)
	Thus the function CPRINT will go through its argument, printing each
	atom it finds, but only printing nonatomic elements if the user is a
	novice.  You are to write this function.  Assume there is a global
	variable called USERNAME, whose value is the last name of the current
	user, and that for each possible user, a property called EXPERIENCED
	exists on his property list, with the value T (if expert) or NIL (if
	he's a novice). By accessing that value, CPRINT can determine whether
	or not to ignore the parenthesized elements of its argument. If not ignored,
	note that the PARENTHESES in the extraneous material should not be printed.
	You may wish to call upon the function PRINC, which prints an atom with
	no extra space or carriage return. You may also then need to refer to the
	atom '| |, which prints as a single blank space. You may also wish to
	define some auxilliary functions (like "Is-Experienced" and "Mapprinc").


4. Notice that when we say ((lambda (x) (PLUS x 5)) (MAXIM INCOMES)) there
	is no reason not to say the same thing more simply as follows:
	(PLUS (MAXIM INCOMES) 5)
	This is due to the fact that the argument x appears only once in the
	entire lambda expression.  You are to write a function which will
	make such simplifications. The function, to be called DELAMB, will take
	an S-expression of the form ((lambda ( v ) e)  q), where v will be some
	variable name, e (the body of the lambda) will be any S-expression, 
	and q (the argument on which the lambda is evaluated) is any S-expression.
	If v appears more than once anywhere inside e, then the value of DELAMB
	is its original argument, unchanged in any way. Otherwise, the value
	will be the expression e, with q substituted for v. You may call upon
	the function SUBST[x,y,z] which substitutes x for y throughout z.
	E.g., (SUBST 'A 'B '(X A B C D)) is (X A A C D).  Note that DELAMB will
	make the simplification mentioned at the beginning of this question,
	but if given as its argument the form
	(lambda (x) (PLUS x (ADD1 x) 5))   (MAXIM INCOMES)) it would not change
	it in any way, because x occurs more than once in the lambda body.
   (a) [16pts] Write the function DELAMB.
   (b) [5pts] According to our above specification, it seems clear that
	(DELAMB '(lambda (Y) (PLUS 3 Y (EVAL Z) 8)) (MAXIM INCOMES))  will
	be simply (PLUS 3 (MAXIM INCOMES) (EVAL Z) 8).  For what value of
	Z might this "get in trouble"; i.e., the EVAL of the original lambda
	yielding a different value than the EVAL of the simplified expression?